/*
 * Copyright (c) 2022.版权所有高金磊
 */

package 领扣算法.AA中等题.太平洋大西洋水流问题;

import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String arg[]){//main--来自高金磊

        new Main().pacificAtlantic(new int[][]{{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}});
    }

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        boolean[][] pac=new boolean[heights.length][heights[0].length];
        boolean[][] alt=new boolean[heights.length][heights[0].length];
        for (int i = 0; i < pac.length; i++) {
            pac[i][0]=true;
            alt[i][alt[0].length-1]=true;
        }
        for (int i = 0; i < pac[0].length; i++) {
            pac[0][i]=true;
            alt[alt.length-1][i]=true;
        }
        boolean flag=true;
        while (flag){
            flag=false;
            for (int i = 1; i < pac.length; i++) {
                for (int j = 1; j < pac[0].length; j++) {
                    if (pac[i][j]){
                        continue;
                    }
                    if (i==pac.length-1&&j==pac[0].length-1)
                    {
                        if ((pac[i-1][j]&&heights[i][j]>=heights[i-1][j])||(pac[i][j-1]&&heights[i][j]>=heights[i][j-1])) {
                            pac[i][j] = true;
                            flag=true;

                        }
                        continue;
                    }
                    if (i==pac.length-1){
                        if ((pac[i-1][j]&&heights[i][j]>=heights[i-1][j])||(pac[i][j-1]&&heights[i][j]>=heights[i][j-1])
                               ||(pac[i][j+1]&&heights[i][j]>=heights[i][j+1])) {
                            pac[i][j] = true;
                            flag=true;

                        }
                        continue;
                    }
                    if (j==pac[0].length-1){
                        if ((pac[i-1][j]&&heights[i][j]>=heights[i-1][j])||(pac[i][j-1]&&heights[i][j]>=heights[i][j-1])
                                ||(pac[i+1][j]&&heights[i][j]>=heights[i+1][j])) {
                            pac[i][j] = true;
                            flag=true;
                        }
                        continue;
                    }
                    if ((pac[i-1][j]&&heights[i][j]>=heights[i-1][j])||(pac[i][j-1]&&heights[i][j]>=heights[i][j-1])
                            ||(pac[i+1][j]&&heights[i][j]>=heights[i+1][j])||(pac[i][j+1]&&heights[i][j]>=heights[i][j+1])) {
                        pac[i][j] = true;
                        flag=true;
                    }

                }
            }
        }
        flag=true;
        while (flag){
            flag=false;
            for (int i = alt.length-2; i >=0 ; i--) {
                for (int j = alt[0].length-2; j >=0 ; j--) {
                    if (alt[i][j])
                        continue;
                    if (i==0&&j==0){
                        if ((alt[i+1][j]&&heights[i+1][j]<=heights[i][j])||(alt[i][j+1]&&heights[i][j+1]<=heights[i][j])){
                            flag=true;
                            alt[i][j]=true;
                        }
                        continue;
                    }
                    if (i==0){
                        if ((alt[i+1][j]&&heights[i+1][j]<=heights[i][j])||
                                (alt[i][j+1]&&heights[i][j+1]<=heights[i][j])||(alt[i][j-1]&&heights[i][j-1]<=heights[i][j])){
                            flag=true;
                            alt[i][j]=true;
                        }
                        continue;
                    }
                    if (j==0){
                        if ((alt[i+1][j]&&heights[i+1][j]<=heights[i][j])||(alt[i-1][j]&&heights[i-1][j]<=heights[i][j])||
                                (alt[i][j+1]&&heights[i][j+1]<=heights[i][j])){
                            flag=true;
                            alt[i][j]=true;
                        }
                        continue;
                    }
                    if ((alt[i+1][j]&&heights[i+1][j]<=heights[i][j])||(alt[i-1][j]&&heights[i-1][j]<=heights[i][j])||
                            (alt[i][j+1]&&heights[i][j+1]<=heights[i][j])||(alt[i][j-1]&&heights[i][j-1]<=heights[i][j])){
                        flag=true;
                        alt[i][j]=true;
                    }
                }
            }
        }
        List<List<Integer>> res=new LinkedList<>();
        for (int i = 0; i < pac.length; i++) {
            for (int j = 0; j < pac[0].length; j++) {
                if (pac[i][j]&&alt[i][j])
                {
                    LinkedList<Integer> middle=new LinkedList<>();
                    middle.add(i);
                    middle.add(j);
                    res.add(middle);
                }
            }
        }
        return res;

    }
}
